// 给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
// 你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
// 思路1，递归
function mergeTrees(root1, root2) {
    if (!root1) {
        return root2
    }
    if (!root2) {
        return root1
    }
    root1.val += root2.val
    root1.left = mergeTrees(root1.left, root2.left)
    root1.right = mergeTrees(root1.right, root2.right)
    return root1
}

// 思路2，层序遍历
function mergeTrees2(root1, root2) {
    if (!root1) {
        return root2
    }
    if (!root2) {
        return root1
    }
    let queue = [root1, root2]
    while (queue.length) {
        let node1 = queue.shift()
        let node2 = queue.shift()
        node1.val += node2.val
        if (node1.left && node2.left) {
            queue.push(node1.left, node2.left)
        }
        if (node1.right && node2.right) {
            queue.push(node1.right, node2.right)
        }
        if (!node1.left) {
            node1.left = node2.left
        }
        if (!node1.right) {
            node1.right = node2.right
        }
    }
    return root1
}

const root1 = {
    val: 1,
    left: {
        val: 3,
        left: {
            val: 5
        }
    },
    right: {
        val: 2
    }
}

const root2 = {
    val: 2,
    left: {
        val: 1,
        right: {
            val: 4
        }
    },
    right: {
        val: 3,
        right: {
            val: 7
        }
    }
}

// console.log(mergeTrees(root1, root2))
console.log(mergeTrees2(root1, root2))